PGMS_67259_경주로 건설

다익스트라(Dijkstra) 알고리즘을 사용해서 방향별 최솟값을 갱신하는 문제
처음에 다익스트라를 떠올렸지만 방향별로 갱신하는 것을 생각 못해서 헤매다가 정답을 봤다

코너 설계 비용은 500 일반 도로 비용은 100이다
방향이 중요한 이유는 어떤 진행 방향인가에 따라서 다음 진로가 바뀌기 때문이다

일반적으로 너비 우선 탐색(BFS)으로 이차원 배열을 탐색할 때는 현재 노드를 최소 거리로 왔다면 다른 경로를 볼 필요가 없다. 왜냐면 다음 진로가 같기 때문이다

다익스트라도 마찬가지다. 현재 노드를 최소 비용으로 도착하지 않았다면 더 이상 그 진로를 볼 필요가 없다

이 문제의 경우 진행 방향에 따라 도로를 만드는 비용이 달라지기 때문에, n*n 크기의 맵을 탐색한다고 생각하면 올바르게 알고리즘을 짤 수 없다. 최소 비용으로 해당 좌표에 도착했다고 하더라도, 진행 방향이 다르다면 다음 진로가 최소 비용을 보장해주지 못한다

그래서 n*n*4크기의 맵을 탐색한다고 봐야한다. 즉, 거리를 저장하는 dis 배열은 3차원 크기를 가져야 한다

import sys
import heapq

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def dijkstra(board, n):
    hq = list()
    dis = [[[sys.maxsize] * 4 for _ in range(n)] for _ in range(n)]
    heapq.heappush(hq, (0, 0, 0, 1))
    heapq.heappush(hq, (0, 0, 0, 2))
    
    dis[0][0][1] = 0
    dis[0][0][2] = 0
    
    while hq:
        cost, x, y, d = heapq.heappop(hq)
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or ny < 0 or nx >= n or ny >= n or board[nx][ny] == 1:
                continue
                
            n_cost = cost + 100 + (500 if (d + i) % 2 == 1 else 0)
            
            # d는 들어온 방향
            if dis[nx][ny][d] >= n_cost:
                dis[nx][ny][d] = n_cost
                heapq.heappush(hq, (n_cost, nx, ny, i))
                
    return min(dis[n-1][n-1])
        
def solution(board):
    return dijkstra(board, len(board))